#include <stdlib.h>

#define LEFT 0
#define RIGHT 1
#define DISTANCE 2

/**
 * Cluster the linkage output.
 *
 * result should be allocated to sizeof(float)*size_y.
 */
extern "C" __declspec(dllexport) void
clustertree(float *result, float *input, const unsigned int size_y, const unsigned int num_clusters)
{
	int i;
	float j;
	unsigned int k;
	float icluster = 0;
	const int n = size_y-num_clusters;
	float *nodeid;
	nodeid = (float*)malloc(n*sizeof(float));

	for (i = size_y-2; i >= n; i--)
	{ 
		k = (int)input[i*3 + LEFT];
		if (k<size_y +1)
		{
			result[k-1] = icluster;
			icluster += 1;
		}
		k = (int)input[i*3 + RIGHT];

		if (k<size_y+1)
		{
			result[k-1] = icluster;
			icluster += 1;
		}
	}

	for (i = 0; i < n; i++) nodeid[i] = -1.0;
	for (i = n-1; i >= 0; i--)
	{
		if(nodeid[i]<0) 
		{ 
			j = icluster;
			nodeid[i] = j;
			icluster = icluster + 1;
		}
		else j = nodeid[i];

		k = (int)input[3*i +LEFT];

		if (k>=size_y+1) nodeid[k-size_y-1] = j; else result[k-1] = j;

		k = (int)input[i*3 + RIGHT];

		if (k>=size_y+1) nodeid[k-size_y-1] = j; else result[k-1] = j;
	}

	free(nodeid);
}
